import java.util.*;

/**
 * 173. 二叉搜索树迭代器
 * https://leetcode-cn.com/problems/binary-search-tree-iterator/
 */
public class Solutions_173 {
    public static void main(String[] args) {
        String treeStr = "[7 3 15 # # 9 20]";
        // 使用工具类，将字符串解析为二叉树对象
        TreeNode root = MyTreeNodeUtils.deserialize(treeStr);

        BSTIterator obj = new BSTIterator(root);
        int res1 = obj.next();  // output: 3
        System.out.println(res1);
        int res2 = obj.next();  // output: 7
        System.out.println(res2);
        boolean res3 = obj.hasNext();  // output: true
        System.out.println(res3);
        int res4 = obj.next();  // output: 9
        System.out.println(res4);
        boolean res5 = obj.hasNext();  // output: true
        System.out.println(res5);
        int res6 = obj.next();  // output: 15
        System.out.println(res6);
        boolean res7 = obj.hasNext();  // output: true
        System.out.println(res7);
        int res8 = obj.next();  // output: 20
        System.out.println(res8);
        boolean res9 = obj.hasNext();  // output: false
        System.out.println(res9);
    }
}

/**
 * 解法二：受控递归（懒加载方式）
 * 思路：并不一次性将二叉树的节点都添加到栈中，而是需要时，再进行添加操作
 */
class BSTIterator {
    Deque<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new ArrayDeque<>();
        // 初始时，先将 root 的最左子树路径，迭代添加到栈中，使最小节点成为栈顶元素
        loadToStack(root);
    }

    void loadToStack(TreeNode root) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    /** @return the next smallest number */
    public int next() {
        // 弹出栈顶元素
        TreeNode minNode = stack.pop();
        if (minNode.right != null) {
            // minNode 的右子树入栈，则右子树中最左侧的节点，
            // 即是 minNode 的后继节点成为栈顶元素
            loadToStack(minNode.right);
        }
        return minNode.val;
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }
}

/**
 * 解法一：扁平化二叉搜索树（23ms）
 * 执行构造方法时，将 root 中的全部节点按中序遍历（右中左顺序）添加到栈中，
 * 保证栈顶元素是最小的节点
 */
class BSTIterator2 {
    Deque<TreeNode> stack;
    Deque<TreeNode> nodes;

    public BSTIterator2(TreeNode root) {
        stack = new LinkedList<>();
        nodes = new LinkedList<>();
        // 中序遍历：右中左，添加 root 节点到栈中，保证栈顶元素是最小的节点值
        loadToStack(root);
    }

    void loadToStack(TreeNode root) {
        TreeNode cur = root;
        // 迭代完成二叉树的中序遍历（右中左顺序）
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                // 添加最右子树的路径
                stack.push(cur);
                cur = cur.right;
            }
            TreeNode node = stack.pop();
            nodes.push(node);
            // 迭代左子树
            cur = node.left;
        }
    }

    /** @return the next smallest number */
    public int next() {
        // 弹出栈顶元素
        return nodes.poll().val;
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !nodes.isEmpty();
    }
}

